#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    reeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    ~TreeNode() {
        if (left) delete left;
        if (right) delete right;
    }
    TreeNode(std::vector<int> vec) {
        std::vector<TreeNode*> nodes;
        this->val = vec[0];
        nodes.push_back(this);
        for (int i = 1; i < vec.size(); ++i) {
            if (vec[i] != -1111)  // use 1111 sign not exist though it's not good
                nodes.push_back(new TreeNode(vec[i]));
            else
                nodes.push_back(nullptr);
        }
        for (int i = 0; i < vec.size() / 2; ++i) {
            if (i * 2 + 1 < vec.size()) nodes[i]->left = nodes[i * 2 + 1];
            if (i * 2 + 2 < vec.size()) nodes[i]->right = nodes[i * 2 + 2];
        }
    }
};

class Solution {
  public:
    TreeNode* balanceBST(TreeNode* root) {
        std::vector<TreeNode*> nodes;
        dfs(root, nodes);
        return build_tree(nodes, 0, nodes.size());
    }

    TreeNode* build_tree(std::vector<TreeNode*>& nodes, int start, int end) {
        if (start >= end) return nullptr;
        int mid = (start + end) / 2;
        auto root = nodes[mid];
        root->left = build_tree(nodes, start, mid);
        root->right = build_tree(nodes, mid + 1, end);
        return root;
    }

    void dfs(TreeNode* root, std::vector<TreeNode*>& nodes) {
        if (not root) return;
        dfs(root->left, nodes);
        nodes.push_back(new TreeNode(root->val));
        dfs(root->right, nodes);
    }
};

int main() {
    TreeNode root(std::vector<int>{1, 2, 3, 4, 5});
    Solution s;
    s.balanceBST(&root);
    return 0;
}
